The present invention relates to layered decomposition of images and, more particularly, to a method of generating out-of-layer pixels for a layer of a decomposed image.
The large size of digital data files required to represent images makes data compression an imperative when storing or transmitting images. On the other hand, compression can be problematic because many images comprise a combination of text, line-art graphics elements, and photographic or natural image elements and compression processes are commonly designed to be more effective with one type of image element than another. For example, JPEG (Joint Photographic Experts Group) (ISO 10918) encoders are designed to most effectively compress the complex multicolor matrix of photographic image elements. Annoying artifacts can appear in decompressed images, especially in the vicinity of sharp color transitions which are common characteristics of graphical and textual elements. On the other hand, the compression process of the JBIG (Joint Bilevel Image Group) standard (ISO/IEC 11544:1993) utilizes arithmetic encoding and is particularly effective in compressing text and graphics but less effective in compressing photographs of natural elements.
One method for improving the efficiency and results of image compression decomposes compound images into layers containing a type or limited number of types of elements that are effectively compressed using a single process. The data of each layer is then compressed with a process that is particularly effective with the type of data contained in the layer. The DRAFT ITU-T RECOMMENDATION T.44 xe2x80x9cMIXED RASTER CONTENT (MRC),xe2x80x9d International Telecommunication Union (ITU), Telecommunication Standardization Sector, October 1997, incorporated herein by reference, specifies the technical features of an imaging format based on segmentation or decomposition of images or pages into multiple layers (planes) according to the type of image element and the application of encoding, spatial resolution, and color resolution processing specific to the types of image elements comprising the layer. Referring to FIG. 1, the ITU recommendation models a page or image 10 as three layers: a background layer 12 containing contone color (continuous tone and palettized color) elements; a foreground layer 14 containing text and line-art graphics, and a bi-level mask layer 16 interposed between the background 12 and foreground 14 layers. The decomposition of an image requires generation of the three layers. The mask is used to select the layer (background or foreground) from which a pixel will be rendered when the image is recomposed. The mask layer is generated by a process that decides whether a pixel of the image 10 belongs in the foreground 14 or the background 12 layer. In the exemplary mask layer 16 a white pixel 18 indicates that the spatially corresponding pixel in the recomposed image is to be obtained from the foreground layer 14. A black pixel 20 in the mask indicates that the spatially corresponding pixel of the recomposed image is to be obtained from the background layer 12.
A second step in the decomposition process is the generation of the foreground 14 and background 12 layers. The first step is analogous to pouring the image 10 through a mask layer 16 comprising a screen with certain pores plugged. When the image 10 is xe2x80x9cpouredxe2x80x9d through the mask 16 the pixels of the background 12 are stopped by the plugged, black pores 20 while the pixels of the foreground layer 14 flow through the open, white pores 18 of the mask. The result of the separation process is a background layer 12 and a foreground layer 14 each comprising xe2x80x9cin-layerxe2x80x9d pixels 22 or pixels that properly belong in the layer and transparent xe2x80x9cout-of-layerxe2x80x9d pixels 24. Out-of-layer pixels 24 are pixels of a layer that spatially correspond to a pixel that is assigned to the other layer by the mask. The xe2x80x9cout of layerxe2x80x9d pixels may be considered to be transparent pixels or xe2x80x9cholesxe2x80x9d in the layer resulting from the layer separation process.
While the out-of-layer pixels are not used and their color values are unimportant for the image recomposition process, the colors of these pixels are important to the efficient compression of the layer and the reduction of artifacts in the recomposed image. If the values chosen for the out-of-layer pixels are inappropriate, the efficiency of the compression process applied to the layer will suffer or the recomposed image may contain artifacts. As an extreme example, if an out-of-layer pixel was assigned its color in the original image in the foreground and background layers, two images identical to the original would be generated by the layer separation process and there would be no value in decomposing the image into layers. For effective compression and reduction of artifacts in the recomposed image, it is desirable to further process the separation layers 12 and 14 to construct a final image decomposition layer by assigning color values to out-of-layer pixels 24 that are consistent with the in-layer pixels and the compression algorithm to be applied to the layer.
R. L. de Querioz described a layered image decomposition in the paper COMPRESSION OF COMPOUND DOCUMENTS, Proceedings 1999 IEEE International Conference on Image Processing, October 1999. The image is decomposed into two layers both of which are to be compressed using a JPEG encoder. The JPEG encoder performs discrete cosine transform (DCT) encoding on 8xc3x978 blocks of pixels and is particularly suited to compressing continuous tone images of natural elements. In this process, if the entire block of pixels comprises out-of-layer pixels, the pixels are assigned a color equivalent to the average color value of the pixels in the previous block. If the pixels of the block are a mixture of in-layer and out-of-layer pixels, a multi-pass algorithm is used to select a value for the out-of-layer pixels. With each pass, the pixels immediately adjacent to any out-of-layer pixel are checked. If any pixels neighboring the out-of-layer pixel are in-layer pixels, the out-of-layer pixel is replaced with the average value of those in-layer pixels and the out-of-layer pixel is designated to be an in-layer pixel. The procedure is repeated until all out-of-layer pixels have been designated as in-layer pixels. Since the JPEG encoder differentially encodes the DC component of the transformed block, it is particularly suited to encoding a layer or image where colors smoothly transition. However, the JPEG encoder is not well suited to image elements having hard edges (typical of text and line art). Palette-based lossless compression is simple and effective for compressing images or layers comprising a limited palette. Averaging the colors of neighboring pixels produces additional colors unduly complicating the palette and reducing the efficiency of the palette-based lossless compression processes.
MacLeod et al., U.S. Pat. No. 5,778,092 disclose a method for plugging holes or generating out-of-layer pixels in a foreground layer for a decomposed image. The method utilizes a sequential two pass examination of the pixels neighboring an out-of-layer pixel. The first pass is a downward examination of neighbors above and left of the out-of-layer pixel or hole. The second examination is an upward pass during which neighbors below and to the right of the out-of-layer pixel are examined. The color assigned to the out-of-layer pixel is the color of the nearest in-layer pixel where nearness is in terms of a four-connected grid. While the method does not create additional colors for pixels, the image must be scanned twice and the results of the scans stored before out-of-layer pixels are generated.
What is desired, therefore, is an efficient method of generating out-of-layer pixels for an image decomposition layer that is described by a limited color palette and which is to be compressed using a palette-based lossless compression method.
The present invention overcomes the aforementioned drawbacks of the prior art by providing a method of generating an out-of-layer pixel of a layer of a decomposed image comprising the steps of identifying a plurality of pixels neighboring the out-of-layer pixel; assigning a default color to the out-of-layer pixel if the pixels of the neighboring plurality are out-of-layer pixels for which no color is assigned; assigning a color predominating for in-layer pixels of the plurality of neighbors to the out-of-layer pixel; assigning a color of a predetermined neighboring pixel to the out-of-layer pixel if equal numbers of the in-layer neighboring pixels are of a plurality of colors; and if no two in-layer neighboring pixels are of the same color, assigning to the out-of-layer pixel a color of a neighboring pixel that is most likely to occur in conjunction with pixels of the colors of the in-layer neighboring pixels. If no two in-layer, neighboring pixels are of the same color, the out-of-layer pixel is assumed, successively, to be of the same color as each of the neighboring pixels. The pixel color combination occurring more often or the sum of the pixel color combinations occurring most often in the layer is used to select the color of the out-of-layer pixel.
A method of generating a layer of a decomposed image is also provided comprising the steps of selecting a pixel of the image; determining if the selected pixel is an in-layer pixel to a layer of the decomposed image; if the selected pixel is an out-of-layer pixel, identifying a plurality of pixels of the decomposition layer neighboring the selected pixel; assigning a default color to a pixel of the decomposition layer spatially corresponding to the selected pixel if all the pixels of the neighboring plurality are out-of-layer pixels; assigning a color predominating for in-layer, neighboring pixels to the spatially corresponding pixel; assigning to the spatially corresponding pixel a color of a predetermined neighboring pixel if equal numbers of the in-layer neighboring pixels are of the same plurality of colors; if no two in-layer neighboring pixels are of the same color, assigning to the spatially corresponding pixel a color of a neighboring pixel that is most likely to occur in conjunction with pixels of the colors of the in-layer neighboring pixels; if the selected pixel is an in-layer pixel, assigning a color of the selected pixel to the spatially corresponding pixel; and storing the color assigned to the spatially corresponding pixel in data of the decomposition layer.